package leetcode_day._2021._202105._1120;

import java.util.*;

/**
 * @author yzh
 * @version 1.0
 * @date 2021/5/20 21:41
 * 前K个高频单词
 * 算法：哈希表  堆(优先队列)
 * 使用优先队列来构建堆
 * 如果队列中不足 k 个，直接插入
 * 反之，则比较出现的词频，如果词频相同，则比较字母
 *
 * 如果不同的单词有相同出现频率，按字母顺序排序, 所以要按照单词从小到大排序
 */
public class _20_692 {

    public List<String> topKFrequent(String[] words, int k) {
        Map<String, Integer> map = new HashMap<>();
        for (String s : words) map.put(s, map.getOrDefault(s, 0) + 1);
        PriorityQueue<Object[]> priorityQueue = new PriorityQueue<>(k, (a, b) -> {
            int c1 = (Integer) a[1], c2 = (Integer) b[1];
            if (c1 != c2) return c1 - c2; // 升序, 从小到大
            String s1 = (String) a[0], s2 = (String) b[0];
            return s2.compareTo(s1); // 降序, 从大到小
        });
        for (Map.Entry<String, Integer> entry : map.entrySet()) {
            if (priorityQueue.size() < k) priorityQueue.add(new Object[]{entry.getKey(), entry.getValue()});
            else {
                int curCount = entry.getValue(), firstCount = (Integer) priorityQueue.peek()[1];
                String firstS = (String) priorityQueue.peek()[0];
                if (curCount > firstCount || curCount == firstCount && entry.getKey().compareTo(firstS) < 0) {
                    priorityQueue.poll();
                    priorityQueue.add(new Object[]{entry.getKey(), entry.getValue()});
                }
            }
        }
        List<String> ans = new ArrayList<>();
        while (!priorityQueue.isEmpty()) ans.add((String) priorityQueue.poll()[0]);
        Collections.reverse(ans);
        return ans;
    }

}
